package top.humbleyuan.tree;

import top.humbleyuan.datastructure.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 21:27
 * @Des 不同的二叉搜索树II
 */
public class LeetCode_95 {

    /**
     * 不同的二叉树2
     * G(n)表示n个数字所有树的list
     *     F(i,n)表示以i为根的情况下的所有树的list
     *     由G(n) = 左 * 右(i<=n)，且有二叉搜索树的特性
     *     即F(i,n) = G(i-1) * G(n-i) 做笛卡尔积
     *     G(n) = F(1,n) + F(2,n) + ... + F(n,n) 加入一个list
     *
     *     G(0) = 1,G(1) = 1
     *     G(2) = F(1,2) + F(2,2) = G(0)*G(1) + G(1)*G(0)
     *     G(3) = F(1,n) + F(2,n) + F(3,n) = G(0)*G(2) + G(1)*G(1) + G(2)*G(0)
     *     ...
     */
    public static void main(String[] args) {
        int n = 3;

        List<TreeNode> treeNodes = new ArrayList<>();

        treeNodes.add(new TreeNode(1));

        for(int i = 2;i <= n;i++) {
            // 对前一个tree[i-1]所有的最后加上数i
            // 添加根为i的数，即在根i的左边加上tree[i-1]中所有tree
            List<TreeNode> tempTrees = new ArrayList<>();
            for (TreeNode treeNode:treeNodes) {
                // 拷贝一份
                TreeNode tempNode = cloneTree(treeNode);

                // 进行根为i的操作
                TreeNode newTree = new TreeNode(i);
                newTree.left = treeNode;
                tempTrees.add(newTree);

                TreeNode temp = cloneTree(tempNode);
                TreeNode head = temp;

                int floor = 0;
                // 进行根为i-1的操作，需要讨论，因为i肯定出现在右子树上，但不确定是那哪一层
                // 循环到没有右孩子为止
                while (temp.right != null) {
                    floor ++;

                    TreeNode cur = new TreeNode(i);
                    cur.left = temp.right;
                    temp.right = cur;

                    tempTrees.add(head);

                    head = cloneTree(tempNode);
                    temp = head;
                    for (int k = 0;k < floor;k++) {
                        temp = temp.right;
                    }
                }
                temp.right = new TreeNode(i);
                tempTrees.add(head);
            }

            treeNodes = new ArrayList<>(tempTrees);

        }

    }

    // 注意树的正确拷贝方式
    public static TreeNode cloneTree(TreeNode treeNode) {
        if(treeNode == null) {
            return null;
        }

        TreeNode newTreeNode = new TreeNode(treeNode.val);

        newTreeNode.left = cloneTree(treeNode.left);
        newTreeNode.right = cloneTree(treeNode.right);

        return newTreeNode;
    }
}
